/*
 * @lc app=leetcode.cn id=430 lang=golang
 * @lcpr version=30118
 *
 * [430] 扁平化多级双向链表
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Prev *Node
 *     Next *Node
 *     Child *Node
 * }
 */

func flatten(root *Node) *Node {
	if root == nil {
		return root
	}
	head, _ := dfs(root)

	// for p := head; p != nil; p = p.Next {
	// 	fmt.Print(p.Val)
	// 	fmt.Print(",")
	// }
	// fmt.Println()

	// for p := tail; p != nil; p = p.Prev {
	// 	fmt.Print(p.Val)
	// 	fmt.Print(",")
	// }
	// fmt.Println()

	return head
}

func dfs(root *Node) (*Node, *Node) {
	if root == nil {
		return root, root
	}

	head := root
	tail := root

	for tail.Next != nil {
		if tail.Child != nil {
			nhead, ntail := dfs(tail.Child)
			tail.Child = nil
			ntail.Next = tail.Next
			nhead.Prev = tail
			tail.Next = nhead
			tail = ntail
			if ntail.Next != nil {
				ntail.Next.Prev = ntail
			}
		}
		if tail.Next != nil {
			tail = tail.Next
		}
	}

	// 此时一定有：tail != nil && tail.Next == nil， 且当前tail 的 Child 还没有被序列化
	if tail.Child != nil {
		nhead, ntail := dfs(tail.Child)
		tail.Child = nil
		ntail.Next = tail.Next
		nhead.Prev = tail
		tail.Next = nhead
		tail = ntail
		if ntail.Next != nil {
			ntail.Next.Prev = ntail
		}
	}

	return head, tail
}

// @lc code=end

/*
// @lcpr case=start
// [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]\n
// @lcpr case=end

// @lcpr case=start
// [1,2,null,3]\n
// @lcpr case=end

// @lcpr case=start
// []\n
// @lcpr case=end

*/

